package com.zklh.leetcode.top100;

/**
 * 乘积最大子数组算法实现
 *
 * @version 1.0
 * @Author tongnan
 * @Date 2023/12/14
 */
public class Solution152 {
    /**
     * 输入: nums = [2,3,-2,4]
     * 输出: 6
     *
     * 输入: nums = [-2,0,-1]
     * 输出: 0
     * @param nums
     * @return
     */
    public int maxProduct(int[] nums) {
        // i 为右边界的极值
        int[] rightMax = new int[nums.length];
        int[] rightMin = new int[nums.length];

        rightMax[0] = nums[0];
        rightMin[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            rightMax[i] = Math.max(Math.max(rightMin[i-1] * nums[i], rightMax[i-1] * nums[i]), nums[i]);
            rightMin[i] = Math.min(Math.min(rightMin[i-1] * nums[i], rightMax[i-1] * nums[i]), nums[i]);
        }

        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            max = Math.max(rightMax[i], max);
        }
        return max;
    }



    public static void main(String[] args) {
        Solution152 solution = new Solution152();
        int[] nums1 = {2,3,-2,4};
        int[] nums2 = {-2,0,-1};
        int[] nums3 = {-3,-1,-1};
        int[] nums4 = {-4, -3};

        System.out.println(solution.maxProduct(nums4));
    }
}